// 判断有向图是否存在环
#include<stdio.h>
#include<stdlib.h>
using namespace std;
#define maxsize 100
int visited[maxsize];
typedef struct Enode{
    int adjvex;
    struct Enode *next;
}*en;
typedef struct Vnode{
    char data;
    struct Enode *firstArc;
}*vn,adjList[maxsize];
typedef struct AGraph{
    int vNum,eNum;
    adjList vertices;
}Graph;

void createGraph(Graph *g){
    int i,j,k;
    printf("\n请输入顶点个数和边的条数:");
    scanf("%d %d",&g->vNum,&g->eNum);
    printf("\n请输入顶点信息:");
    for(k=0;k<g->vNum;k++){
        getchar();
        scanf("%c",&g->vertices[k].data);
        g->vertices[k].firstArc=NULL;
    }
    printf("\n请输入边的信息:\n");
    for(k=0;k<g->eNum;k++){
        scanf("%d %d",&i,&j);
        en enode=(en)malloc(sizeof(struct Enode));
        enode->adjvex=j;
        enode->next=g->vertices[i].firstArc;
        g->vertices[i].firstArc=enode;
        // 无向图省略
    }
}
void printAdjList(Graph g){
    for(int i=0;i<g.vNum;i++){
        printf("%c->",g.vertices[i].data);
        en p=(en)malloc(sizeof(struct Enode));
        p=g.vertices[i].firstArc;
        while(p){
            printf("%c->",g.vertices[p->adjvex].data);
            p=p->next;
        }
        printf("\n");
    }
}
bool dfs(Graph g,int v){
    visited[v]=true;
    for(en p=g.vertices[v].firstArc;p!=NULL;p=p->next){
        if(visited[p->adjvex]){
            return true;
        }
        if(!visited[p->adjvex]){
            return dfs(g,p->adjvex);
        }
    }
    return false;
}
bool dfs_traverse(Graph g){
    for(int i=0;i<g.vNum;i++){
        visited[i]=false;
    }
    for(int i=0;i<g.vNum;i++){
        if(!visited[i]){
            if(dfs(g,i)==true){
                return true;
            }
        }
        
    }
    return false;
}

int main(){
    Graph g;
    createGraph(&g);
    printAdjList(g);
    printf("\n是否存在环:%d",dfs_traverse(g));
    return 0;
}